using System;
using System.Collections.Generic;

// 邻接矩阵图测试类
public class AdjacentMatrixTest
{
    public static void RunTest()
    {
        Console.WriteLine("========== 邻接矩阵图测试 ==========");
        //测试(V = {0, 1, 2})
        DirectedWeightedGraphMatrix testGraph = new(3);
        //0->1 01
        testGraph.AddEdge(0, 1, 1);
        //0->2 02
        testGraph.AddEdge(0, 2, 2);
        //1->2 12
        testGraph.AddEdge(1, 2, 12);
        //2->0 20
        testGraph.AddEdge(2, 0, 20);

        Console.WriteLine("\n按 Enter 键继续测试...");
        Console.ReadLine();

        //删除0->2
        testGraph.RemoveEdge(0, 2);
        Console.WriteLine("0->2是否存在:" + testGraph.HasEdge(0, 2));

        Console.WriteLine("\n按 Enter 键继续测试...");
        Console.ReadLine();

        Console.WriteLine("0->1的权重应该是 01 ->:" + testGraph.GetWeight(0, 1));

        Console.WriteLine("\n按 Enter 键继续测试...");
        Console.ReadLine();

        testGraph.AddEdge(1, 0, 10);
        List<int> neighbors = testGraph.GetNeighbors(1);
        foreach (var neighbor in neighbors)
        {
            Console.WriteLine("1的邻居有" + neighbor + " 的权重应该是" + testGraph.GetWeight(1, neighbor));
        }

        Console.WriteLine("\n按 Enter 键继续测试...");
        Console.ReadLine();

        Console.WriteLine("所有边:" + testGraph.GetAllEdges().Count);
    }
}
//有向加权图 矩阵邻接实现
public class DirectedWeightedGraphMatrix{
    private int[][] graph;
    public DirectedWeightedGraphMatrix(int n){
        graph = new int[n][];
        for(int i = 0; i < n; i++){
            graph[i] = new int[n];
        }
    }
    public void AddEdge(int from, int to, int weight){
        graph[from][to] = weight;
    }
    public void RemoveEdge(int from, int to){
        graph[from][to] = 0;
    }
    public bool HasEdge(int from, int to){
        return graph[from][to] != 0;
    }
    public int GetWeight(int from, int to){
        return graph[from][to];
    }
    public List<int> GetNeighbors(int from){
        List<int> neighbors = new List<int>();
        for(int i = 0; i < graph[from].Length; i++){
            if(graph[from][i] != 0){
                neighbors.Add(i);
            }
        }
        return neighbors;
    }
    public List<int> GetAllEdges(){
        List<int> edges = new List<int>();
        for(int i = 0; i < graph.Length; i++){
            for(int j = 0; j < graph[i].Length; j++){
                if(graph[i][j] != 0){
                    edges.Add(graph[i][j]);
                }
            }
        }
        return edges;
    }
}